{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# CS 162 Scheduling Lab"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import deque\n",
    "import matplotlib.pyplot as plt\n",
    "import numpy as np\n",
    "from random import expovariate\n",
    "%matplotlib inline\n",
    "\n",
    "import doctest\n",
    "def test(fun, verbose=False):\n",
    "    doctest.run_docstring_examples(fun, None, name=fun.__name__, verbose=verbose)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Task Model\n",
    "\n",
    "Our model of a task ignores what computation and I/O it actually does; we are only interested in its scheduling events.  This is captured by three basic parameters, all of which operate in an abstract time unit, say ms:\n",
    "\n",
    "* arrival - the time at which the task is first initiated\n",
    "* total - total execution time of the task (how long it runs).  Generally we don't know this value, although to simulate oracle scheduling we could peek.  It determines when the task exits.\n",
    "* burst_fun - a function that returns the length of the next CPU burst, given its elapsed execution time.  This can be viewed as the time to the next syscall.  A value of 0 is taken to be run-to-completion.  A periodic application simply returns a constant, the number of time units in each burst duration.  A stochastic model is obtained by drawing a value according to some distribution.\n",
    "* io_burst_fun - a function that returns the length of time the task spends waiting for I/O etc.\n",
    "\n",
    "\n",
    "\n",
    "The overall workload is described by a stream of such tasks."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Task(object):\n",
    "    \"\"\" Model of a program task: \n",
    "    arrives as a certain time and then alternates CPU and IO bursts of possibly varying length\n",
    "    till it has executed for a certain amount of CPU time\n",
    "    \"\"\"\n",
    "    task_number = 0   # Unique identifier for each task\n",
    "    \n",
    "    def __init__(self, arrival, total, burst_fun, io_burst_fun):\n",
    "        \"\"\"Create a task with specified arrival, total run time, and functions modeling burst lengths.\"\"\"\n",
    "        Task.task_number += 1\n",
    "        self.task = Task.task_number\n",
    "        self.arrival_time = arrival\n",
    "        self.total_run_time = total\n",
    "        self.cpu_burst = burst_fun\n",
    "        self.io_burst = io_burst_fun\n",
    "        return None\n",
    "    \n",
    "    def __repr__(self):\n",
    "        return \"Task {} arr:{} len:{}\".format(self.task, self.arrival_time, self.total_run_time)\n",
    "\n",
    "class TaskStream(object):\n",
    "    \"\"\"Stream of tasks arriving as time moves forward\"\"\"\n",
    "    def __init__(self, tasks):\n",
    "        self.tasks = sorted(tasks, key=lambda x: x.arrival_time)\n",
    "    \n",
    "    def next_arrival(self):\n",
    "        if not self.tasks:\n",
    "            return None\n",
    "        return self.tasks[0].arrival_time\n",
    "    \n",
    "    def enter_tasks(self, time):\n",
    "        \"\"\"Generate a thread for and remove each tasks arriving upto time. \"\"\"\n",
    "        for task in self.tasks.copy():\n",
    "            if task.arrival_time <= time:\n",
    "                self.tasks.remove(task)\n",
    "                yield Thread(task)\n",
    "\n",
    "    def show(self):\n",
    "        for t in self.tasks:\n",
    "            print(t)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Thread Model\n",
    "\n",
    "The execution of the steps of a task is emulated by `Thread` class `run` method.  It is passed the length of the CPU quanta up to which may run, with `q == 0` indicating indefinitely, i.e., to the end of its burst or to completion.  Based on its internal bookkeeping, i.e., where the thread is in the current burst and the task time to completion, \n",
    "`run` determines how long the thread will run and returns that value along with a status indicating whether the\n",
    "thread continues to run at the end of the quantum (\"cpu\"), blocked before the quantum (\"io\"), or ran to completion (\"done\"). \n",
    "\n",
    "One subtlety is that if a tasks is scheduled multiple times to complete a burst, the `burst_fun` is not used until the task is rescheduled after the completes, i.e., it would be returning from the syscall."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Thread(object):\n",
    "    \"\"\" Model of a running process thread.\n",
    "    \n",
    "    Each time a task is run, it executes for 1 or more time units, until it\n",
    "    - completes a cpu burst\n",
    "    - exhausts a quanta (under preemptive scheduling), or\n",
    "    - completes\n",
    "    \"\"\"\n",
    "    \n",
    "    def __init__(self, task):\n",
    "        \"\"\"Create a thread object with characteristics of modeled task.\"\"\"\n",
    "        self.task = task\n",
    "        self.elapsed_time = 0\n",
    "        self.last_queued = None\n",
    "        self.wait_time = 0\n",
    "        self.remaining_burst = None\n",
    "        self.wakeup_time = None\n",
    "    \n",
    "    def __repr__(self):\n",
    "        return \"Thread {} | elapsed: {} wait:{} rbrst:{} wakeup: {}\".format(self.task, \n",
    "                                    self.elapsed_time, self.wait_time, self.remaining_burst, self.wakeup_time)\n",
    "        \n",
    "    def remaining(self):\n",
    "        return self.task.total_run_time - self.elapsed_time\n",
    "    \n",
    "    def run(self, q=0):\n",
    "        \"\"\" Advance the thread for up to q units (q==0 is nonpremptive) till cpu burst completes or done\"\"\"\n",
    "        io_time = None\n",
    "        if (self.remaining_burst):  # Still completing burst\n",
    "            if q > 0:                 # preemptive : run for Q, burst done, or pgm done\n",
    "                run_len = min(q, self.remaining_burst, self.remaining())\n",
    "            else:                      # non-preemptive : run till burst or pgm down\n",
    "                run_len = min(self.remaining_burst, self.remaining())\n",
    "            self.remaining_burst -= run_len\n",
    "            self.elapsed_time += run_len\n",
    "            if self.remaining_burst:                    # Still working on prior CPU burst\n",
    "                status = 'cpu'\n",
    "            else:\n",
    "                status = 'io'                            # completed the burst, start wait\n",
    "                io_time = self.task.io_burst(self.elapsed_time) \n",
    "        else:                                                             # starting a new burst\n",
    "            burst = self.task.cpu_burst(self.elapsed_time)   \n",
    "            if burst == 0 and q == 0:                                # run till done\n",
    "                run_len = self.remaining()           \n",
    "            elif burst == 0:                                           # run till Q or done\n",
    "                run_len = min(q, self.remaining())  \n",
    "            elif q == 0:                                               # run till burst or done\n",
    "                run_len = min(burst, self.remaining())\n",
    "            else:                                                         # run till Q, burst, or done\n",
    "                run_len = min(q, burst, self.remaining())\n",
    "\n",
    "            self.elapsed_time += run_len\n",
    "            if burst == 0:\n",
    "                status = 'cpu'\n",
    "            elif run_len < burst:                           # Continue CPU burst\n",
    "                self.remaining_burst = burst - run_len\n",
    "                status = 'cpu'\n",
    "            else:                                          # Completed CPU burst, start I/O wait\n",
    "                status = 'io'\n",
    "                io_time = self.task.io_burst(self.elapsed_time) \n",
    "\n",
    "        if self.remaining() <= 0:             # override status if thread finished\n",
    "            status = 'done'\n",
    "        return run_len, status, io_time"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Processor  Model\n",
    "\n",
    "We also have a very simple model of a process.  It moves forward in time, either sitting idle or executing a task.  \n",
    "\n",
    "The one complexity is that if tasks arrive or IO completes while a thread is being run, they need to be entered into the ready queue.  Thus, our processor model needs access to the task stream and the enqueue method of the scheduler for such starts and restarts."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Machine(object):\n",
    "    \"\"\"\n",
    "    Simulate machine.  \n",
    "    Time moves forward, either idling or running - this is the only property of the machine\n",
    "    Along the way, it consumes the list of future tasks, builds a log of its actions,\n",
    "    and records the summary of every thread.\n",
    "    \"\"\"\n",
    "    def __init__(self, task_stream, ready, verbose=False):\n",
    "        self.time = 0   \n",
    "        \n",
    "        self.log = [(0, 'start')]\n",
    "        self.threads = []\n",
    "        self.verbose = verbose\n",
    "        \n",
    "        self.io = []\n",
    "        self.future = task_stream\n",
    "        self.ready = ready\n",
    "        self._arrivals()\n",
    "        \n",
    "    def pending(self):\n",
    "        return self.future.tasks or self.io\n",
    "    \n",
    "    def next_start(self):\n",
    "        \"\"\"Return time of next start or -1 if none.\"\"\"\n",
    "        next_taskstart = self.future.next_arrival()\n",
    "        if self.io and next_taskstart:\n",
    "            return min(next_taskstart, min([t.wakeup_time for t in self.io]))\n",
    "        elif self.io:\n",
    "            return min([t.wakeup_time for t in self.io])\n",
    "        else:\n",
    "            return next_taskstart\n",
    "        \n",
    "    def io_wait(self, thread, wait_time):\n",
    "        \"\"\" Put thread completed cpu burst with positive wait time in IO queue till wakeup\"\"\"\n",
    "        thread.wakeup_time = self.time + wait_time\n",
    "        self.io.append(thread)\n",
    "        if self.verbose:\n",
    "            print(\"{0}: IO wait for Task {1} for duration {2}\".format(self.time, thread.task.task, wait_time))\n",
    "        self.log.append((self.time, 'io wait', thread.task, wait_time))\n",
    "\n",
    "    def _arrivals(self):\n",
    "        # Collect new tasks that arrived while this was idling or running\n",
    "        for thread in self.future.enter_tasks(self.time):\n",
    "            self.threads.append(thread)\n",
    "            self.ready.arrive(thread, thread.task.arrival_time)\n",
    "            if self.verbose:\n",
    "                print(\"{0}: Arrival of Task {1} (ready queue length = {2})\".format(thread.task.arrival_time, thread.task.task, len(self.ready)))\n",
    "            self.log.append((thread.task.arrival_time, 'arrive', thread.task, len(self.ready)))\n",
    "            \n",
    "        # Collect threads that completed IO\n",
    "        for thread in self.io.copy():\n",
    "            if thread.wakeup_time <= self.time:\n",
    "                self.io.remove(thread)\n",
    "                self.ready.wake(thread, thread.wakeup_time)\n",
    "                if self.verbose:\n",
    "                    print(\"{0}: Wakeup of Task {1} (ready queue length = {2})\".format(thread.wakeup_time, thread.task.task, len(self.ready)))\n",
    "                self.log.append((thread.wakeup_time, 'wakeup', thread.task, len(self.ready)))\n",
    "            \n",
    "    \n",
    "    def idle(self):\n",
    "        \"\"\"\n",
    "        Idle from current time till next task arrival or IO wait completes.  \n",
    "        Enter all tasks that arrive or IO complete during idle period ready queue.\n",
    "        \"\"\"\n",
    "        if self.pending():\n",
    "            idle_time = self.next_start()\n",
    "            if idle_time > 0:\n",
    "                if self.verbose:\n",
    "                    print(\"{0}: Idle for {1}\".format(self.time, idle_time - self.time))\n",
    "                self.log.append((self.time, 'idle', idle_time - self.time))\n",
    "                self.time = idle_time          # Processor moves forward in time\n",
    "                self._arrivals()    \n",
    "    \n",
    "    def run(self, run_time, thread):\n",
    "        \"\"\" Advance machine time for run_time.  \n",
    "        Enter new tasks and IO completes during run into ready queue\n",
    "        \"\"\"\n",
    "        if self.verbose:\n",
    "            print(\"{0}: Run Task {1} for duration {2} (ready queue length = {3})\".format(self.time, thread.task.task, run_time, len(self.ready)))\n",
    "        self.log.append((self.time, 'run', thread.task, run_time, len(self.ready), self.ready.weight()))\n",
    "        self.time += run_time           # All we do to run is move time forward\n",
    "        self._arrivals()\n",
    "            \n",
    "    def stop(self):\n",
    "        if self.verbose:\n",
    "            print(\"{0}: Stop\".format(self.time))\n",
    "        self.log.append((self.time, 'stop'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Example Schedulers\n",
    "\n",
    "Each scheduler consists of a loop over the workload and a data structure that implements its policy.  The\n",
    "schedule presents the thread with its quanta to the thread model to determine how long it retains the CPU\n",
    "and the status at the end of that time, i.e. CPU, I/O, Done.  \n",
    "\n",
    "Based on that determination, it allows the machine to advance to that point in time.  Along the way, tasks\n",
    "may arrive or threads may complete their I/O wait, so the machine will invoke methods in the scheduler\n",
    "appropriately."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## FCFS and Round Robin\n",
    "\n",
    "Both are built on a simple FIFO queue, the latter with preemption using fixed quanta.  The enqueue and dequeue operation take a simulated time as which it occurs so that they can update observational data carried in the task structure for analysis and reporting."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class FIFOQueue:\n",
    "    \"\"\" FIFO Queue of tasks to be scheduled \"\"\"\n",
    "    def __init__(self):\n",
    "        self.queue = deque()\n",
    "    \n",
    "    def enqueue(self, thread, at_time):\n",
    "        thread.last_queued = at_time\n",
    "        self.queue.appendleft(thread)\n",
    "        \n",
    "    def dequeue(self, at_time):\n",
    "        thread = self.queue.pop()\n",
    "        thread.wait_time += at_time - thread.last_queued\n",
    "        return thread\n",
    "    \n",
    "    def arrive(self, thread, at_time):\n",
    "        self.enqueue(thread, at_time)\n",
    "    \n",
    "    def wake(self, thread, at_time):\n",
    "        self.enqueue(thread, at_time)\n",
    "    \n",
    "    def empty(self):\n",
    "        return len(self.queue) == 0\n",
    "    \n",
    "    def __len__(self):\n",
    "        return len(self.queue)\n",
    "    \n",
    "    def weight(self):\n",
    "        return sum([x.task.total_run_time - x.elapsed_time for x in self.queue])\n",
    "    \n",
    "    def show(self):\n",
    "        for e in self.queue:\n",
    "            print(\" \", e)\n",
    "            \n",
    "def scheduler(tasks, q, queue_class, verbose=False):\n",
    "    remaining = TaskStream(tasks)\n",
    "    ready = queue_class()\n",
    "    cpu = Machine(remaining, ready, verbose)\n",
    "\n",
    "    while not ready.empty() or cpu.next_start():\n",
    "        if ready.empty():\n",
    "            cpu.idle()\n",
    "        else:     \n",
    "            thread = ready.dequeue(cpu.time)\n",
    "            run_time, status, io_time = thread.run(q)\n",
    "            cpu.run(run_time, thread)\n",
    "            if status == 'io' and io_time > 0:\n",
    "                cpu.io_wait(thread, io_time)\n",
    "            elif status != 'done':\n",
    "                ready.enqueue(thread, cpu.time)    \n",
    "    cpu.stop()\n",
    "    return cpu\n",
    "    \n",
    "def round_robin(tasks, q, verbose=False):\n",
    "    return scheduler(tasks, q, FIFOQueue, verbose)\n",
    "    \n",
    "def fcfs(tasks, verbose=False):\n",
    "    return round_robin(tasks, 0, verbose)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Helper Functions for Burst Modeling"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Burst functions and factories\n",
    "\n",
    "def indefinite(run_time):\n",
    "    \"\"\"Run till done\"\"\"\n",
    "    return 0;\n",
    "\n",
    "def nowait(run_time):\n",
    "    \"\"\"No I/O wait.\"\"\"\n",
    "    return 0;\n",
    "\n",
    "def make_periodic(duration):\n",
    "    \"\"\"Bursts of constant duration for run or io, i.e., periodic.\"\"\"\n",
    "    return lambda rt: duration\n",
    "\n",
    "def make_exponential(mean_duration):\n",
    "    \"\"\"Bursts of duration drawn from an exponential distribution of specified mean.\"\"\"\n",
    "    return lambda rt: round(expovariate(1.0/mean_duration))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def analyze(thrds):\n",
    "    \"\"\"For now just print it out\"\"\"\n",
    "    print(\"---\")\n",
    "    for t in thrds:\n",
    "        print(t)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Study Cases"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Task.task_number = 0\n",
    "\n",
    "workload1 = [\n",
    "    Task(0, 4, indefinite, nowait),\n",
    "    Task(1, 7, indefinite, nowait),\n",
    "    Task(2, 2, make_periodic(1), make_periodic(4)),     # run 1, IO 4, run 1\n",
    "    Task(3, 3, make_periodic(1), make_periodic(1))      # run 1, IO 1, run 1, IO 1, run 1\n",
    "]\n",
    "\n",
    "# Idle two short, 1 long, four short\n",
    "workload2 = [\n",
    "    Task(10,  30, indefinite, nowait),\n",
    "    Task(20,  30, indefinite, nowait),\n",
    "    Task(30, 100, indefinite, nowait),\n",
    "    Task(40,  30, indefinite, nowait),\n",
    "    Task(60,  30, indefinite, nowait),\n",
    "    Task(80,  30, indefinite, nowait),\n",
    "    Task(100,  30, indefinite, nowait)\n",
    "]\n",
    "\n",
    "workload3 = [\n",
    "    Task(0, 4, make_periodic(2), make_periodic(1)),     # run 2, IO 1, run 2\n",
    "    Task(1, 7, indefinite, nowait),\n",
    "    Task(2, 2, make_periodic(1), make_periodic(2)),     # run 1, IO 2, run 1\n",
    "    Task(3, 3, make_periodic(6), make_periodic(1))      # run 1, IO 1, run 1, IO 1, run 1\n",
    "]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example Testing Code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def test_fcfs_workload1():\n",
    "    \"\"\" Test FCFS on workload1\n",
    "    \n",
    "    >>> _ = fcfs(workload1, True)\n",
    "    0: Arrival of Task 1 (ready queue length = 1)\n",
    "    0: Run Task 1 for duration 4 (ready queue length = 0)\n",
    "    1: Arrival of Task 2 (ready queue length = 1)\n",
    "    2: Arrival of Task 3 (ready queue length = 2)\n",
    "    3: Arrival of Task 4 (ready queue length = 3)\n",
    "    4: Run Task 2 for duration 7 (ready queue length = 2)\n",
    "    11: Run Task 3 for duration 1 (ready queue length = 1)\n",
    "    12: IO wait for Task 3 for duration 4\n",
    "    12: Run Task 4 for duration 1 (ready queue length = 0)\n",
    "    13: IO wait for Task 4 for duration 1\n",
    "    13: Idle for 1\n",
    "    14: Wakeup of Task 4 (ready queue length = 1)\n",
    "    14: Run Task 4 for duration 1 (ready queue length = 0)\n",
    "    15: IO wait for Task 4 for duration 1\n",
    "    15: Idle for 1\n",
    "    16: Wakeup of Task 3 (ready queue length = 1)\n",
    "    16: Wakeup of Task 4 (ready queue length = 2)\n",
    "    16: Run Task 3 for duration 1 (ready queue length = 1)\n",
    "    17: Run Task 4 for duration 1 (ready queue length = 0)\n",
    "    18: Stop\n",
    "    \"\"\"\n",
    "    return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test(test_fcfs_workload1, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def test_round_robin():\n",
    "    \"\"\" Test round robin on workload1\n",
    "    \n",
    "    >>> _ = round_robin(workload1, 2, True)\n",
    "    0: Arrival of Task 1 (ready queue length = 1)\n",
    "    0: Run Task 1 for duration 2 (ready queue length = 0)\n",
    "    1: Arrival of Task 2 (ready queue length = 1)\n",
    "    2: Arrival of Task 3 (ready queue length = 2)\n",
    "    2: Run Task 2 for duration 2 (ready queue length = 2)\n",
    "    3: Arrival of Task 4 (ready queue length = 3)\n",
    "    4: Run Task 3 for duration 1 (ready queue length = 3)\n",
    "    5: IO wait for Task 3 for duration 4\n",
    "    5: Run Task 1 for duration 2 (ready queue length = 2)\n",
    "    7: Run Task 4 for duration 1 (ready queue length = 1)\n",
    "    8: IO wait for Task 4 for duration 1\n",
    "    8: Run Task 2 for duration 2 (ready queue length = 0)\n",
    "    9: Wakeup of Task 3 (ready queue length = 1)\n",
    "    9: Wakeup of Task 4 (ready queue length = 2)\n",
    "    10: Run Task 3 for duration 1 (ready queue length = 2)\n",
    "    11: Run Task 4 for duration 1 (ready queue length = 1)\n",
    "    12: IO wait for Task 4 for duration 1\n",
    "    12: Run Task 2 for duration 2 (ready queue length = 0)\n",
    "    13: Wakeup of Task 4 (ready queue length = 1)\n",
    "    14: Run Task 4 for duration 1 (ready queue length = 1)\n",
    "    15: Run Task 2 for duration 1 (ready queue length = 0)\n",
    "    16: Stop\n",
    "    \"\"\"\n",
    "    return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test(test_round_robin, True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exploring Behavior on CPU-only Workloads"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# FCFS exhibits convoy effect\n",
    "\n",
    "fcfs_cpu = fcfs(workload2, True)\n",
    "analyze(fcfs_cpu.threads)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Round robin services the later arriving short ones, more evenly distributing wait\n",
    "\n",
    "rr40_CPU = round_robin(workload2, 40, True)\n",
    "analyze(rr40_CPU.threads)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Round robin with short quanta causes the interactive jobs to wait\n",
    "\n",
    "rr20_cpu = round_robin(workload2, 20, True)\n",
    "analyze(rr20_cpu.threads)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Problem 1: Scheduling Simulator Implementation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Complete the implementations of the SRTF and MLFQ schedulers below."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Shortest Remaining Time First\n",
    "\n",
    "Use our oracle knowledge of the future of each job to select the one that will finish soonest.  This inherits from the generic queue providing a specialized dequeue."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class SRTFQueue(FIFOQueue):\n",
    "    \"\"\" Shortest remaining time first queue - with perfect knowledge \"\"\"\n",
    "    def dequeue(self, at_time):\n",
    "        # YOUR CODE HERE\n",
    "        pass\n",
    "        \n",
    "def srtf(tasks, q, verbose=False):\n",
    "    return scheduler(tasks, q, SRTFQueue, verbose)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def test_srtf1():\n",
    "    \"\"\" Test SRTF\n",
    "    \n",
    "    >>> _ = srtf(workload1, 2, True)\n",
    "    0: Arrival of Task 1 (ready queue length = 1)\n",
    "    0: Run Task 1 for duration 2 (ready queue length = 0)\n",
    "    1: Arrival of Task 2 (ready queue length = 1)\n",
    "    2: Arrival of Task 3 (ready queue length = 2)\n",
    "    2: Run Task 1 for duration 2 (ready queue length = 2)\n",
    "    3: Arrival of Task 4 (ready queue length = 3)\n",
    "    4: Run Task 3 for duration 1 (ready queue length = 2)\n",
    "    5: IO wait for Task 3 for duration 4\n",
    "    5: Run Task 4 for duration 1 (ready queue length = 1)\n",
    "    6: IO wait for Task 4 for duration 1\n",
    "    6: Run Task 2 for duration 2 (ready queue length = 0)\n",
    "    7: Wakeup of Task 4 (ready queue length = 1)\n",
    "    8: Run Task 4 for duration 1 (ready queue length = 1)\n",
    "    9: Wakeup of Task 3 (ready queue length = 2)\n",
    "    9: IO wait for Task 4 for duration 1\n",
    "    9: Run Task 3 for duration 1 (ready queue length = 1)\n",
    "    10: Wakeup of Task 4 (ready queue length = 2)\n",
    "    10: Run Task 4 for duration 1 (ready queue length = 1)\n",
    "    11: Run Task 2 for duration 2 (ready queue length = 0)\n",
    "    13: Run Task 2 for duration 2 (ready queue length = 0)\n",
    "    15: Run Task 2 for duration 1 (ready queue length = 0)\n",
    "    16: Stop\n",
    "    \"\"\"\n",
    "    return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# If you implemented SRTF correctly, this test should pass\n",
    "test(test_srtf1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Shortest Remaining Time first sets aside the long one and services all the short ones.\n",
    "\n",
    "def test_srtf2():\n",
    "    \"\"\" Test SRTF\n",
    "    \n",
    "    >>> _ = srtf(workload2, 5, True)\n",
    "    0: Idle for 10\n",
    "    10: Arrival of Task 5 (ready queue length = 1)\n",
    "    10: Run Task 5 for duration 5 (ready queue length = 0)\n",
    "    15: Run Task 5 for duration 5 (ready queue length = 0)\n",
    "    20: Arrival of Task 6 (ready queue length = 1)\n",
    "    20: Run Task 5 for duration 5 (ready queue length = 1)\n",
    "    25: Run Task 5 for duration 5 (ready queue length = 1)\n",
    "    30: Arrival of Task 7 (ready queue length = 2)\n",
    "    30: Run Task 5 for duration 5 (ready queue length = 2)\n",
    "    35: Run Task 5 for duration 5 (ready queue length = 2)\n",
    "    40: Arrival of Task 8 (ready queue length = 3)\n",
    "    40: Run Task 8 for duration 5 (ready queue length = 2)\n",
    "    45: Run Task 8 for duration 5 (ready queue length = 2)\n",
    "    50: Run Task 8 for duration 5 (ready queue length = 2)\n",
    "    55: Run Task 8 for duration 5 (ready queue length = 2)\n",
    "    60: Arrival of Task 9 (ready queue length = 3)\n",
    "    60: Run Task 8 for duration 5 (ready queue length = 3)\n",
    "    65: Run Task 8 for duration 5 (ready queue length = 3)\n",
    "    70: Run Task 9 for duration 5 (ready queue length = 2)\n",
    "    75: Run Task 9 for duration 5 (ready queue length = 2)\n",
    "    80: Arrival of Task 10 (ready queue length = 3)\n",
    "    80: Run Task 9 for duration 5 (ready queue length = 3)\n",
    "    85: Run Task 9 for duration 5 (ready queue length = 3)\n",
    "    90: Run Task 9 for duration 5 (ready queue length = 3)\n",
    "    95: Run Task 9 for duration 5 (ready queue length = 3)\n",
    "    100: Arrival of Task 11 (ready queue length = 4)\n",
    "    100: Run Task 11 for duration 5 (ready queue length = 3)\n",
    "    105: Run Task 11 for duration 5 (ready queue length = 3)\n",
    "    110: Run Task 11 for duration 5 (ready queue length = 3)\n",
    "    115: Run Task 11 for duration 5 (ready queue length = 3)\n",
    "    120: Run Task 11 for duration 5 (ready queue length = 3)\n",
    "    125: Run Task 11 for duration 5 (ready queue length = 3)\n",
    "    130: Run Task 10 for duration 5 (ready queue length = 2)\n",
    "    135: Run Task 10 for duration 5 (ready queue length = 2)\n",
    "    140: Run Task 10 for duration 5 (ready queue length = 2)\n",
    "    145: Run Task 10 for duration 5 (ready queue length = 2)\n",
    "    150: Run Task 10 for duration 5 (ready queue length = 2)\n",
    "    155: Run Task 10 for duration 5 (ready queue length = 2)\n",
    "    160: Run Task 6 for duration 5 (ready queue length = 1)\n",
    "    165: Run Task 6 for duration 5 (ready queue length = 1)\n",
    "    170: Run Task 6 for duration 5 (ready queue length = 1)\n",
    "    175: Run Task 6 for duration 5 (ready queue length = 1)\n",
    "    180: Run Task 6 for duration 5 (ready queue length = 1)\n",
    "    185: Run Task 6 for duration 5 (ready queue length = 1)\n",
    "    190: Run Task 7 for duration 5 (ready queue length = 0)\n",
    "    195: Run Task 7 for duration 5 (ready queue length = 0)\n",
    "    200: Run Task 7 for duration 5 (ready queue length = 0)\n",
    "    205: Run Task 7 for duration 5 (ready queue length = 0)\n",
    "    210: Run Task 7 for duration 5 (ready queue length = 0)\n",
    "    215: Run Task 7 for duration 5 (ready queue length = 0)\n",
    "    220: Run Task 7 for duration 5 (ready queue length = 0)\n",
    "    225: Run Task 7 for duration 5 (ready queue length = 0)\n",
    "    230: Run Task 7 for duration 5 (ready queue length = 0)\n",
    "    235: Run Task 7 for duration 5 (ready queue length = 0)\n",
    "    240: Run Task 7 for duration 5 (ready queue length = 0)\n",
    "    245: Run Task 7 for duration 5 (ready queue length = 0)\n",
    "    250: Run Task 7 for duration 5 (ready queue length = 0)\n",
    "    255: Run Task 7 for duration 5 (ready queue length = 0)\n",
    "    260: Run Task 7 for duration 5 (ready queue length = 0)\n",
    "    265: Run Task 7 for duration 5 (ready queue length = 0)\n",
    "    270: Run Task 7 for duration 5 (ready queue length = 0)\n",
    "    275: Run Task 7 for duration 5 (ready queue length = 0)\n",
    "    280: Run Task 7 for duration 5 (ready queue length = 0)\n",
    "    285: Run Task 7 for duration 5 (ready queue length = 0)\n",
    "    290: Stop\n",
    "    \"\"\"\n",
    "    return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# If you implemented SRTF correctly, this test should pass\n",
    "test(test_srtf2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Copy-and-paste the output of this cell as your answer to Problem 1(a).\n",
    "_ = srtf(workload3, 2, True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### MLFQ with Two Levels\n",
    "\n",
    "A foreground interactive queue with a small quantum and a background CPU-bound queue with a large quantum."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class TwoLevelFeedbackQueue(object):\n",
    "    \"\"\" Dual Queue of tasks to be scheduled \"\"\"\n",
    "    def __init__(self, q_int, q_cpu):\n",
    "        self.queue = deque()\n",
    "        self.q = q_int\n",
    "        self.q_cpu = q_cpu\n",
    "        self.cpu_queue = deque()\n",
    "    \n",
    "    def enqueue(self, thread, at_time):\n",
    "        \"\"\"Insert into interactive\"\"\"\n",
    "        # YOUR CODE HERE\n",
    "        pass\n",
    "        \n",
    "    def enqueue_cpu(self, thread, at_time):\n",
    "        \"\"\"Insert into non-interactive\"\"\"\n",
    "        # YOUR CODE HERE\n",
    "        pass\n",
    "        \n",
    "    def dequeue(self, at_time):\n",
    "        # YOUR CODE HERE\n",
    "        pass\n",
    "    \n",
    "    def arrive(self, thread, at_time):\n",
    "        self.enqueue(thread, at_time)\n",
    "    \n",
    "    def wake(self, thread, at_time):\n",
    "        self.enqueue(thread, at_time)\n",
    "    \n",
    "    def empty(self):\n",
    "        return not self.queue and not self.cpu_queue\n",
    "    \n",
    "    def __len__(self):\n",
    "        return len(self.queue) + len(self.cpu_queue)\n",
    "    \n",
    "    def weight(self):\n",
    "        return sum([t.remaining() for t in self.queue]) + sum([t.remaining() for t in self.cpu_queue])\n",
    "\n",
    "\n",
    "def mlfq2(tasks, q1, q2, verbose=False):\n",
    "    remaining = TaskStream(tasks)\n",
    "    ready = TwoLevelFeedbackQueue(q1, q2)\n",
    "    cpu = Machine(remaining, ready, verbose)\n",
    "\n",
    "    while not ready.empty() or cpu.next_start():\n",
    "        if ready.empty():\n",
    "            cpu.idle()\n",
    "        else:     \n",
    "            thread, quanta = ready.dequeue(cpu.time)\n",
    "            run_time, status, io_time = thread.run(quanta)\n",
    "            cpu.run(run_time, thread)\n",
    "            \n",
    "            if status == 'io' and io_time > 0:\n",
    "                cpu.io_wait(thread, io_time)\n",
    "            elif status == 'cpu':\n",
    "                ready.enqueue_cpu(thread, cpu.time)\n",
    "            elif status != 'done':                \n",
    "                ready.enqueue(thread, cpu.time)      \n",
    "    cpu.stop()\n",
    "    return cpu"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def test_mlfq21():\n",
    "    \"\"\" Test MLFQ2\n",
    "    \n",
    "    >>> _ = mlfq2(workload1, 2, 4, True)\n",
    "    0: Arrival of Task 1 (ready queue length = 1)\n",
    "    0: Run Task 1 for duration 2 (ready queue length = 0)\n",
    "    1: Arrival of Task 2 (ready queue length = 1)\n",
    "    2: Arrival of Task 3 (ready queue length = 2)\n",
    "    2: Run Task 2 for duration 2 (ready queue length = 2)\n",
    "    3: Arrival of Task 4 (ready queue length = 3)\n",
    "    4: Run Task 3 for duration 1 (ready queue length = 3)\n",
    "    5: IO wait for Task 3 for duration 4\n",
    "    5: Run Task 4 for duration 1 (ready queue length = 2)\n",
    "    6: IO wait for Task 4 for duration 1\n",
    "    6: Run Task 1 for duration 2 (ready queue length = 1)\n",
    "    7: Wakeup of Task 4 (ready queue length = 2)\n",
    "    8: Run Task 4 for duration 1 (ready queue length = 1)\n",
    "    9: Wakeup of Task 3 (ready queue length = 2)\n",
    "    9: IO wait for Task 4 for duration 1\n",
    "    9: Run Task 3 for duration 1 (ready queue length = 1)\n",
    "    10: Wakeup of Task 4 (ready queue length = 2)\n",
    "    10: Run Task 4 for duration 1 (ready queue length = 1)\n",
    "    11: Run Task 2 for duration 4 (ready queue length = 0)\n",
    "    15: Run Task 2 for duration 1 (ready queue length = 0)\n",
    "    16: Stop\n",
    "    \"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# If you implemented MLFQ2 correctly, this test should pass\n",
    "test(test_mlfq21)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Dual queue recognizes the long one after 1st quantum and moves to the long queue\n",
    "# No oracle information is needed.\n",
    "\n",
    "def test_mlfq22():\n",
    "    \"\"\" Test MLFQ2\n",
    "    \n",
    "    >>> _ = mlfq2(workload2, 50, 200, True)\n",
    "    0: Idle for 10\n",
    "    10: Arrival of Task 5 (ready queue length = 1)\n",
    "    10: Run Task 5 for duration 30 (ready queue length = 0)\n",
    "    20: Arrival of Task 6 (ready queue length = 1)\n",
    "    30: Arrival of Task 7 (ready queue length = 2)\n",
    "    40: Arrival of Task 8 (ready queue length = 3)\n",
    "    40: Run Task 6 for duration 30 (ready queue length = 2)\n",
    "    60: Arrival of Task 9 (ready queue length = 3)\n",
    "    70: Run Task 7 for duration 50 (ready queue length = 2)\n",
    "    80: Arrival of Task 10 (ready queue length = 3)\n",
    "    100: Arrival of Task 11 (ready queue length = 4)\n",
    "    120: Run Task 8 for duration 30 (ready queue length = 4)\n",
    "    150: Run Task 9 for duration 30 (ready queue length = 3)\n",
    "    180: Run Task 10 for duration 30 (ready queue length = 2)\n",
    "    210: Run Task 11 for duration 30 (ready queue length = 1)\n",
    "    240: Run Task 7 for duration 50 (ready queue length = 0)\n",
    "    290: Stop\n",
    "    \"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# If you implemented MLFQ2 correctly, this test should pass\n",
    "test(test_mlfq22)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Copy-and-paste the output of this cell as your answer to Problem 1(b).\n",
    "_ = mlfq2(workload3, 2, 4, True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Problem 2: Approaching 100% Utilization"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def make_exp_arrivals(arrival_rate, service_time, n):\n",
    "    \"\"\"Make n tasks of exponential distributed arrival intervals and lengths\"\"\"\n",
    "    arrivals = np.cumsum(np.random.exponential(1 / arrival_rate, n))\n",
    "    lengths = [service_time for _ in range(n)]\n",
    "    return [Task(arr, run, indefinite, nowait) for arr, run in zip(arrivals, lengths)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# These functions may (or may not) be useful for you to implement\n",
    "\n",
    "def cpuUtilization(cpulog):\n",
    "    # Given the Machine's log (list of tuples), computes the average CPU utilization\n",
    "    # YOUR CODE HERE\n",
    "    return 0\n",
    "\n",
    "def responseTimes(cpulog):\n",
    "    # Given the Machine's log, computes the response time of each task, and returns a list containing them\n",
    "    # YOUR CODE HERE\n",
    "    return [0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# l and lmbdas are \"recommended values\" that you can change if desired\n",
    "l = 10\n",
    "lmbdas = np.array((0.2, 0.5, 0.7, 0.8, 0.9, 0.93, 0.95, 0.97, 0.99)) / l\n",
    "\n",
    "# Decrease this when developing in case it takes too long\n",
    "TRIALS = 100\n",
    "\n",
    "response_time_medians = []\n",
    "response_time_95th_percentiles = []\n",
    "utilizations = []\n",
    "for lmbda in lmbdas:\n",
    "    trial_utilizations = []\n",
    "    trial_medians = []\n",
    "    trial_95ths = []\n",
    "    \n",
    "    for _ in range(TRIALS):\n",
    "        # YOUR CODE HERE\n",
    "        pass\n",
    "    \n",
    "    response_time_medians.append(np.mean(trial_medians))\n",
    "    response_time_95th_percentiles.append(np.mean(trial_95ths))\n",
    "    utilizations.append(np.mean(trial_utilizations))\n",
    "    \n",
    "    # This takes a while to run so this print statement lets us track progress\n",
    "    print(\"Finished\", lmbda)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.xlabel(\"Arrival Rate (lambda)\")\n",
    "plt.ylabel(\"Utilization\")\n",
    "plt.plot(lmbdas, utilizations)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.xlabel(\"Arrival Rate ($\\lambda$)\")\n",
    "plt.ylabel(\"Response Time\")\n",
    "plt.plot(lmbdas, response_time_95th_percentiles, label=\"95th percentile\")\n",
    "plt.plot(lmbdas, response_time_medians, label=\"median\")\n",
    "plt.legend()\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Problem 3: Fairness for CPU Bursts"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import bisect\n",
    "\n",
    "def create_problem3_task(lmbda, num_bursts):\n",
    "    # YOUR CODE HERE\n",
    "    pass\n",
    "\n",
    "def create_problem3_workload(lmbda, num_bursts):\n",
    "    task_S = create_problem3_task(lmbda, num_bursts)\n",
    "    task_T = create_problem3_task(lmbda, num_bursts)\n",
    "    return task_S, task_T"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Feel free to change this while developing if it takes too long to run\n",
    "TRIALS = 10000\n",
    "N = 1.1\n",
    "\n",
    "unfair_count = 0\n",
    "fair_count = 0\n",
    "\n",
    "for _ in range(TRIALS):\n",
    "    fcfs_cpu = fcfs(create_problem3_workload(1.0, 100), False)\n",
    "    elapsed_0 = fcfs_cpu.threads[0].elapsed_time\n",
    "    elapsed_1 = fcfs_cpu.threads[1].elapsed_time\n",
    "    if elapsed_0 / elapsed_1 > N or elapsed_1 / elapsed_0 > N:\n",
    "        unfair_count += 1\n",
    "    else:\n",
    "        fair_count += 1\n",
    "        \n",
    "print(\"Fraction of runs that were unfair:\", unfair_count / (fair_count + unfair_count))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Other Interesting Simulations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here are some other interesting types of graphs you can make, that might be useful to you as you complete the assignment."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Useful functions to process the logs\n",
    "\n",
    "def showQlen(cpulog):\n",
    "    times = [x[0] for x in cpulog if x[1] == 'run']\n",
    "    lengths = [x[4] for x in cpulog if x[1] == 'run']\n",
    "    plt.plot(np.repeat(times,2)[1:], np.repeat(lengths,2)[0:-1])\n",
    "    \n",
    "def showQweight(cpulog):\n",
    "    times = [x[0] for x in cpulog if x[1] == 'run']\n",
    "    weights = [x[5] for x in cpulog if x[1] == 'run']\n",
    "    plt.plot(np.repeat(times,2)[1:], np.repeat(weights,2)[0:-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Create tasks with exponentially distributed arrival times and run lengths\n",
    "# The utilization is essentially the ratio of the means, but be careful as it gets loaded.\n",
    "utilization = 0.9\n",
    "interval = 40\n",
    "run_length = interval*utilization\n",
    "etasks = make_exp_arrivals(1 / interval, run_length, 200)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ecpu_fcfs = fcfs(etasks)\n",
    "wait_fcfs = sum([x.wait_time for x in ecpu_fcfs.threads])\n",
    "ecpu_rr = round_robin(etasks, 5)\n",
    "wait_rr = sum([x.wait_time for x in ecpu_rr.threads])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "wait_fcfs, wait_rr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "showQlen(ecpu_fcfs.log)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "showQlen(ecpu_rr.log)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "showQweight(ecpu_fcfs.log)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "showQweight(ecpu_rr.log)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
